package com.example.dict.utils.Dictionary.Operations;

import com.example.dict.data.WordLoader;
import com.example.dict.utils.Dictionary.dictionaryOperations;

/**
 *
 * 平衡二叉树实现
 * @author wey
 * */
public class AvlTree implements dictionaryOperations {


    /**
     * 全局字典
     * */
    static AvlTree dictionary;


    /**
     * 前缀树根节点
     * 每个字母都对应一棵树， 减少查找次数
     */
    static AvlTreeNode[] catalog = new AvlTreeNode[26];

    /**
     * 初始化字典
     */
    private AvlTree() {
    //        dictionary = new AvlTree();
    }

    /**
     * 获取字典
     * @return 返回字典
     * */
    public static AvlTree acquire() {
        if (null == dictionary) {
            dictionary = new AvlTree();

            for (char letter = 'a'; letter <= 'z'; letter++) {
                String src = "dictionary_storage/" + letter + ".txt";
                WordLoader wordLoader = new WordLoader(dictionary, src);
                wordLoader.start();
            }
        }

        return dictionary;
    }


    /**
     * 翻译单词
     *
     * @param word 单词小写
     * @return 翻译
     */
    @Override
    public String translate(String word) {
        if (null == word || word.isEmpty()) {
            return null;
        }
        AvlTreeNode root = catalog[word.charAt(0) - 'a'];

        while (null != root) {

            if (word.equals(root.word)) return root.translation;

            root = (word.compareTo(root.word) < 0) ? root.left : root.right;
        }

        return null;
    }

    /**
     * 翻译
     * 汉 -> 英
     * @param word 词语
     * @return translation 翻译
     * */
    @Override
    public String translateC2E(String word) {
        if (null == word || word.isEmpty()) {
            return null;
        }
        String ans = "";
        for(AvlTreeNode root : catalog) {
            String tmp = "";
            if (null != (tmp = preOrder(word, root))) {
                ;ans += "\n" + tmp;

            }
        }
        return ans.isEmpty() ? null : ans;
    }

    /**
     *
     * 前序遍历
     * @param word 汉语
     * @param root 单词列表
     * @return 英文翻译 不存在则返回空值
     * */
    private String preOrder(String word, AvlTreeNode root) {
        // 1. 如果节点为空，直接返回 null
        if (root == null) {
            return null;
        }

        // 2. 如果当前节点的翻译包含目标词，返回该节点的单词
        if (root.translation.contains(word)) {
            return root.word + " " + root.translation;
        }

        // 3. 否则递归遍历左子树和右子树
        String leftResult = preOrder(word, root.left);
        if (leftResult != null) {
            return leftResult; // 如果左子树找到结果，返回
        }

        return preOrder(word, root.right); // 否则继续遍历右子树
    }


    /**
     * 收录到字典
     *
     * @param word        单词
     * @param translation 翻译
     */
    @Override
    public void insert(String word, String translation) {
        if (null == word || word.isEmpty() || null == translation || translation.isEmpty(
        )) {
            return;
        }

        catalog[word.charAt(0) - 'a'] = insert(catalog[word.charAt(0) - 'a'], word, translation);
    }

    /**
     * 收录到字典
     *
     * @param root        子树
     * @param word        单词
     * @param translation 翻译
     */
    private AvlTreeNode insert(AvlTreeNode root, String word, String translation) {
        if (null == root) {
            root = new AvlTreeNode(word, translation);
        }
        if (word.compareTo(root.word) > 0) {
            root.right = insert(root.right, word, translation);
        }
        else if (word.compareTo(root.word) < 0) {
            root.left = insert(root.left, word, translation);
        }

        return reBalance(root);
    }

    /**
     * 删除单词
     * @param word 单词
     * */
    @Override
    public void delete(String word) {
        if (null == word || word.isEmpty()) {
            return;
        }
        catalog[word.charAt(0) - 'a'] = delete(catalog[word.charAt(0) - 'a'], word);

    }


    /**
     * 删除单词
     *
     * @param root 子树
     * @param word 单词
     */
    private AvlTreeNode delete(AvlTreeNode root, String word) {
        if (null == root) { return null; }

        if (word.compareTo(root.word) > 0) {
            root.right = delete(root.right, word);
        } else if (word.compareTo(root.word) < 0) {
            root.left = delete(root.left, word);
        } else {
            if (null != root.right) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return reBalance(root);

    }

    /**
     * 自平衡
     *
     * @param root 子树根节点
     * @return 返回新的根节点
     */
    private AvlTreeNode reBalance(AvlTreeNode root) {
        int factor = getBalanceFactor(root);
        if (factor > 1 && getBalanceFactor(root.left) > 0) {
            return rightRotate(root);
        } else if (factor > 1 && getBalanceFactor(root.right) <= 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        } else if (factor < -1 && getBalanceFactor(root.right) < 0) {
            return leftRotate(root);
        } else if (factor < -1 && getBalanceFactor(root.left) >= 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }


    /**
     * 返回某个节点的高度
     *
     * @param root 根节点
     * @return 高度
     */
    private int height(AvlTreeNode root) {
        return null == root ? 0 :Math.max(height(root.left), height(root.right)) + 1;
    }

    /**
     * 获取某个树的平衡因子
     *
     * @param root 树的根节点
     * @return 平衡因子（左子树高度 - 右子树高度）
     */
    private int getBalanceFactor(AvlTreeNode root) {
        if (null == root) {return 0;}
        int l = 0;
        int r = 0;
        if (null != root.left) l = root.left.height;
        if (null != root.right) r = root.right.height;
        return l - r;
    }

    /**
     * 右旋 --> 顺时针
     * 当前节点root
     * 左孩子left
     * 右孩子right
     */
    private AvlTreeNode rightRotate(AvlTreeNode root) {
        AvlTreeNode left = root.left;
        root.left = left.right;
        left.right = root;
        left.height = Math.max(height(left.right), height(left.left)) + 1;
        root.height = Math.max(height(root.left), height(root.right)) + 1;

        return left;
    }

    /**
     * 左旋 --> 逆时针
     * 当前节点root
     * 左孩子left
     * 右孩子right
     */
    private AvlTreeNode leftRotate(AvlTreeNode root) {

        AvlTreeNode right = root.right;

        root.left = right.left;

        right.left = root;

        right.height = Math.max(height(right.left), height(right.right)) + 1;
        root.height = Math.max(height(root.left), height(root.right)) + 1;

        return right;
    }
    /**
     * AVL树节点
     * */
    private static class AvlTreeNode {
        public String word;
        public String translation;

        public int height = 0;

        public AvlTreeNode left, right;
        public AvlTreeNode(String word, String translation) {
            this.word = word;
            this.translation = translation;
        }
    }

//    public String[] like
}
